-
-
Photo: John Cairns
Faculty hiring in our Department: We have 2 faculty positions for recruitment in
the 2026-2027 academic year. Details will be available
here.
Prospective PhD students:
Information about how to apply (to start in Autumn of 2027) is here:
https://www.ox.ac.uk/admissions/graduate/courses/dphil-computer-science.
You can read about my research interests below.
Prospective students should feel free to get in touch if any
of these problems sounds interesting, or if you have other related
ideas in algorithms or complexity theory.
Research Interests
My work is in the intersection of maths and computer science.
Specifically, I work on the design and analysis of randomised algorithms.
Randomised algorithms arise in many computational
contexts including
communication and information spread in networks,
analysing computational models from statistical physics (and other models where
local interactions influence global structure), and learning.
My research focuses on the rigorous, mathematical
analysis of these algorithms - proving
results about how long the algorithms take, and how accurate they are.
I am also interested in related questions from computational complexity
where the goal is to figure out which computational problems can be solved with fast (randomised)
algorithms and which problems provably can't be solved with fast algorithms.
This research is part of the
Algorithms
and Complexity Theory research theme
at Oxford. More widely, it is at the intersection of combinatorics, probability,
and computer science.
Recent results, current projects, and potential PhD projects:
- Contention resolution.
A contention resolution protocol is a simple randomised algorithm which
is used by independent agents to access a shared resource.
These algorithms give rise to difficult and interesting mathematical questions that apply in natural settings.
In the basic model, agents arrive over time, according to a probability
distribution, and have no way to communicate with each other except by attempting to access the resource.
If two agents attempt access at the same time, they "collide" and must try again later. A
backoff protocol is a simple randomised algorithm that agents use to determine when to attempt
access and when to wait. The simplest example is binary exponential backoff
where an agent that has already collided k times makes a random decision at each step,
attempting access with probability
2−k and waiting with probability 1-2-k.
Based on the model of
Frank Kelly,
David Aldous proved that binary exponential backoff is unstable
for any positive rate of arrival,
in the sense that
the underlying random process is not positive recurrent. Informally, this says
that the number of waiting agents builds up over time, even if the rate at which they arrive is arbitrarily low.
Aldous conjectured in 1987 that the same is true for any backoff protocol. After lots of work,
John Lapinskas and I finally proved this in 2026 (the paper is
here). There are lots of interesting open problems, both
in the original model of Kelly, and in other models where contention is
mitigated by the presence of queues, as in
this
paper with
Hesham Al-Ammal and
Phil MacKenzie, or where arrivals are adversarial,
as in this paper by Bender, Kopelowitz, Kuszmaul, and
Pettie.
- Spin systems: sampling and approximate
counting.
One of the most important domains where randomised algorithms are studied is the area of
spin systems. In a spin system, a configuration assigns a "spin" to every vertex of a graph. Spins interact locally along the
edges of the graph, and these interactions give rise to a global distribution on configurations, called the Gibbs
distribution. A famous example is the Ising model. Research in
our area focuses on
determining which model parameters give rise to
fast algorithms for sampling configurations from the Gibbs distribution. Most of my research in this area is joint with
Andreas Galanis and our joint students.
Here is a paper with
our jointly-supervised PhD student,
Paulina Smolarova.
This paper gives a fast algorithm in a setting where the underlying graph is
random (so there are two levels of randomness). Sometimes, it is possible to give fast algorithms on
random graphs in parameter regimes where
it is conjectured that fast algorithms don't exist for worst-case graphs. There are plenty
of open questions about identifying the boundary between where fast algorithms exist and where they don't. Andreas and I are
interested in supervising more PhD students in this area (and related areas).
Many important properties of a spin system can be determined by estimating a function
called its "partition function".
I won't give technical details here, but you can find a very gentle introduction
to a related type of partition function (along with a reference to more of our research in this area)
here
.
The research field that studies algorithms for estimating partition functions is called
"computational counting".
The study of counting complexity goes back
to Les Valiant in the 1970s, but in the
context of randomness and approximation
there are additional challenges.
Here
is an early paper with
Martin Dyer,
Catherine Greenhill, and
Mark Jerrum, which identifies a
key complexity class for approximate counting, centred around a
problem called
#BIS, which is the problem of approximately counting the
independent sets of a bipartite graph. By now there are many
computational problems and classes of computational problems which
are known to be equivalent to #BIS, but we still don't know whether
it even has a fast approximation algorithm (with or without randomness), and this is a
tantalising open problem.
Here is a paper with Jerrum
explaining the relationship between #BIS and spin systems.
- Analysing processes on networks.
Some of my research involves the study of random processes on graphs. For example,
the Moran process is a process which models the spread of genetic mutations in graphs. The goal is to
derive rigorous probabilistic bounds on how these mutations spread over time (as a function of the graph).
Some of my work in the area includes
this paper
(joint with Galanis, Andreas Goebel,
Lapinskas, and
Dave Richerby)
and
this paper (joint with Lapinskas and Richerby).
There are lots of open problems. For example, not much is known when there are several types of mutation, and not much is known about
convergence times on specific families of graphs.
There are also other interesting related models. For example, the voter model, which
models the spread of competing ideas in social networks.
Here
is a recent paper with Galanis and our jointly supervised PhD student
Xandru Mifsud.
analysing a random walk on an evolving random cluster configuration. The random cluster model is another model
related to spin systems. Random walks on randomly evolving environments is a popular research area.
- Approximately counting graph homomorphisms and
related structures
A lot of progress in approximate counting (including randomised
approximate counting) has come from understanding
key graph structures such as
graph homomorphisms.
Often the key ideas come from the study of the structures themselves
(which turn out to be complicated and fascinating!).
Standa Zivny
and I are interesting in jointly superivising a PhD in this area.
Here is a joint paper
with our previous jointly-supervised PhD student
Jacob Focke (and with Marc Roth)
which uses methods related to graph homomorphisms to obtain
approximate-counting results relevant to databases.
A recent paper with Roth (see here)
uses this kind of analysis to deterermine the fine-grained complexity of counting subgraphs, modulo 2.
My AI Policy
AI is a useful tool, and we need to learn how to use it constructively in mathematics.
Mathematicians don't fully agree about AI use,
so this needs to be discussed before starting each new collaboration.
As of now (25 October 2026)
there are many models for post-AI mathematical research. Here is what I think about some of them.
- Using AI as a tool for learning or for doing routine tasks: It is very valuable to use LLMs to learn.
We should all be doing this.
Generative AI is excellent for search.
It enables us to look things up without even knowing what they are called!
It is also obviously sensible to use generative AI for routine tasks like making LaTeX pictures and diagrams.
- Writing papers reporting AI discoveries:
As I have written in my Thoughts about Maths and AI Page, we are currently in an interim period
where many of our open problems can be solved by one-shot AI prompts (asking AI models to solve the problems without significant human contribution).
Many of my colleagues are providing such prompts and turning the results into
papers. I don't want to participate in this activity and I don't think these papers should be accepted by conferences or journals.
- Expository papers: Expository writing has traditionally received too little reward in mathematics. AI-written proofs currently
lack good explanation. I am not sure whether this will remain true, but while it is true, it is especially valuable to provide
high-level exposition. Here I don't mean merely taking an AI-generated result, checking it, and dumping it into a paper. Rather, I mean something deeper,
slower, and more comprehensive: extracting ideas and methods; putting different ideas together; finding the essence; simplifying;
pushing the ideas as far as possible; developing
understanding and explaining the big picture.
-
Good old-fashioned maths: Most of the ordinary problems that we work on
have the property that, while we can't solve them now, there is a real possibility that next week's AI model will be able to solve them.
That's fine. We should continue to work on these problems. Our goal is mathematical understanding, and we get most of this from the
journey - from the failed attempts, from the structures that we consider. Most of the value comes from the process, not from the final one-bit answer.
For this kind of collaboration,
I would expect collaborators to agree in advance not to throw the problem at AI. I would also expect collaborators to consult
with each other before using AI to obtain pieces of the proof (such as proofs of routine lemmas).
If AI is used for any of the mathematics
(which would only be after agreement)
then I would
expect proper disclosure following the principles of the Leiden declaration.
- Using AI as a tool to tackle very hard problems over long periods of time: The landscape of mathematical problems is infinite,
and there are plenty of obvious open problems that are currently beyond the reach of AI, and which seem likely to remain so (though
this is hard to predict!).
I'm thinking here of problems that we would hope to solve over decades, or at least over many years.
For these problems, AI may turn out to be an excellent tool. For example, it may speed up the consideration (and likely rejection) of particular avenues.
I'm open to AI use on projects of
this type, though I still think that collaborators should agree about it in advance, and that proper disclosure should follow.
Links